%%%----------------------------------------------------------
\chapter{Tracking multiple points in image sequences}
%%%----------------------------------------------------------
\label{cha:Trackingpoints}
\section{Problem}
In an image sequence are some points moving around. The human eye is in most cases capable of tracking the points motion. All points have the same color and size so for the computer all points look the same. For preventing finding wrong points, by noise, in a real movie we use synthetic sequences. The image sequence should be evaluated and the three best possible images should be printed.

To compute the trajectories of the lines we have to do some simplifications. The speed and direction of the points change in a nature way. So we can use basic heuristics to evaluate the image sequence.

\section{Solution}
For computing this problem I decided to use the Brute Force algorithm instead of the Greedy-Exchange-Algorithm. 
\subsection{Original image sequence}
In figure ~\ref{fig:08_original} you can see some frames of an original image sequence. For this images the points are increased to 3x3 pixel to see them better. The video file you can find in the video folder \footnote{Original video /images/sample-trajectories-stack1x1.tif}.

\begin{figure}
	\centering
	\includegraphics[width=.3\textwidth]{08_original-1}
	\includegraphics[width=.3\textwidth]{08_original-2}
	\includegraphics[width=.3\textwidth]{08_original-3}
	\caption{Some frames of an original image sequence.}
	\label{fig:08_original}
\end{figure}

\subsection{Algorithm work flow}
The brute force algorithm find all possible combination of points and calculate the path coherence for each line. The path coherence will show us the best fitting lines.

At first we find every point in each frame and store them. Than we find the nearest points, in frame 2, to the points of frame 1. After that we create the Array for all the possible lines. Because he have the solutions for frame 1 and 2 we create an array with parameters as much columns as frames and number of points to the power of columns -1. Than we set the first and the second column of this array with the calculated point number. Now we fill the array with all possible point combinations. For our example video we have 5 points each frame and 10 frames that gives us an array with 10 columns and 1 953 125 rows.

The next step is to calculate the coherence for each possible line by using the path coherence equations of the lecture. The best fitting lines will be drawn to an image.


\section{Implementation}
The implementation is connected to the work flow I already described. For calculating the connection of the points of the first and the second frame using  the theorem of Pythagoras.

\begin{lstlisting}
int[] sndRow = new int[points.size()];
for(int i = 0; i < points.size(); i++) {
    Point P1 = allPoints[0][i];
    double dist = Double.MAX_VALUE;
    int x = 0;
    for(int j = 0; j < points.size(); j++) {
        Point P2 = allPoints[1][j];
        double d = Math.sqrt(Math.pow(P1.x - P2.x, 2)+Math.pow(P1.y - P2.y, 2));
        if(d < dist) {
            dist = d;
            x = j;
        }
    }
    sndRow[i] = x;
}
\lstinputlisting[frame=single, language=Java, numbers=left]
\end{lstlisting}


\subsection{Memory problem with trajectories array}
Like mentioned we get an array with 1 953 125 rows and 10 columns with int values. This array and the other variables will rise the memory consumption of the virtual machine up to 2.2GB of RAM. So we have to increase the memory of the virtual machine for ImageJ in its config file. 

"C:\Program Files\Java\jre7\bin\javaw.exe -Xmx5000m -XX:+AggressiveHeap -cp ij.jar ij.ImageJ"

Now ImageJ can use up to 5GB Ram, the command AggressiveHeap is used because many people had issues with more than 2.5GB on 64bin machines. The virtual machine RAM should not be higher than 3/4th of the physical memory of the computer.

\subsection{Coherence calculation}
By using the equations of the lecture I don't get good coherence values so i decided to add additional calculations for a better weighting.

\subsubsection{Distance}
If the distance between 2 points is bigger than a distance threshold than I add -8000 to the coherence value.

\subsubsection{Distance change}
If the distance changes more than a threshold I add -5000 to the coherence value. 
\begin{lstlisting}
if(distP1P2-distP2P3 < distanceThreshold) {
    summe += -5000;
}
\lstinputlisting[frame=single, language=Java, numbers=left]
\end{lstlisting}


\subsubsection{Angle}
If the angle between the Line1 and Line2 is more than 85$^\circ$ or less than -85$^\circ$ I add -500000 to the coherence. If the angle is between -85$^\circ$ and 85$^\circ$ than I add a angle dependent value. This calculation has to decide if the path goes from left ot right and right to left.

\begin{lstlisting}
if(p1.x > p2.x && p2.x > p3.x) {
    tanA = Math.atan2(p1.y-p2.y, p1.x-p2.x);
    tanB = Math.atan2(p2.y-p3.y, p2.x-p3.x);
    if(Math.abs(tanA-tanB) > Math.toRadians(85)) {
        summe += -50000;
    } else {
        summe -= 30*Math.abs(tanB-tanA);
    }
} else {
    tanA = Math.atan2(p2.y-p1.y, p2.x-p1.x);
    tanB = Math.atan2(p3.y-p2.y, p3.x-p2.x);
    if(Math.abs(tanA-tanB) > Math.toRadians(85)) {
        summe += -50000;
    } else {
        summe -= 30*Math.abs(tanA-tanB);
    }
}
\lstinputlisting[frame=single, language=Java, numbers=left]
\end{lstlisting}

With this calculations we get an image with some errors. You see it in image ~\ref{fig:08_samePoint} that some points are used by two lines. To prevent this I check if some points are used by two lines and if so I take the next best line. The method checkIfPointsUsedTwice get the following parameters. A list of all saved lines for the image as tn and the line i want to add. 

\begin{figure}
	\centering
	\includegraphics[width=.75\textwidth]{08_BruteForce_SamePoint}
	\caption{Some points are used by two lines.}
	\label{fig:08_samePoint}
\end{figure}

\begin{lstlisting}
private boolean checkIfPointsUsedTwice(ArrayList<TrajNode> tn, int[] is2) {
		if(tn.size() > 0)
		{
			for(TrajNode t : tn) 
			{
				int[] is = t.array;
				for(int i = 0; i < is.length; i++)
				{
					if(is[i] == is2[i])
					{
						return true;
					}
				}
			}
		}
		return false;
	}
	\lstinputlisting[frame=single, language=Java, numbers=left]
\end{lstlisting}

\section{Result}
The resulting image with all implemented corrections and checks looks very plausible. See image ~\ref{fig:08_final}

\begin{figure}
	\centering
	\includegraphics[width=.75\textwidth]{08_BruteForce_Final}
	\caption{Image of the best found lines.}
	\label{fig:08_final}
\end{figure}
